package com.xieyong.leetcode;

import java.util.ArrayList;
import java.util.List;

public class Leetcode440 {
    public static void main(String[] args) {
        Leetcode440 leetcode = new Leetcode440();
        int integers = leetcode.findKthNumber(13, 2);
        System.out.println(integers);
    }

    public int findKthNumber(int n, int k) {
        int curint = 1;
        k--;
        while (k > 0) {
            int next = getnext(curint, n);
            if (next <= k) {
                k -= next;
                curint++;
            } else {
                curint *= 10;
                k--;
            }
        }
        return curint;
    }

    private int getnext(int curint, int n) {
        int res = 0;
        long first = curint;
        long last = curint;
        while (first <= n) {
            res += Math.min(last, n) - first + 1;
            first = first * 10;
            last = last * 10 + 9;

        }
        return res;
    }


//    超出内存限制
//    public int findKthNumber(int n, int k) {
//        int res = 1;
//        List<Integer> reslist = new ArrayList<>();
//        for (int i = 1; i < 10; i++) {
//            if (i <= n) {
//                reslist.add(i);
//                if (reslist.size() == k) {
//                    res = reslist.get(k - 1);
//                }
//                int next = getres(n,k,i,reslist);
//                if (next != -1) {
//                    res = next;
//                }
//            }
//        }
//        return res;
//    }
//
//    public int getres (int n,int k, int parent,List<Integer> list)  {
//        int res = -1;
//        for (int i = 0; i < 10; i++) {
//            int temp = parent*10+i;
//            if (temp <= n && temp != 0) {
//                list.add(temp);
//                if (list.size() == k) {
//                    res = list.get(k - 1);
//                }
//                int next = getres(n,k,temp,list);
//                if (next != -1) {
//                    res = next;
//                }
//            }
//        }
//        return res;
//    }

}
